The present invention is directed to the feature-correspondence problem encountered in object recognition, alignment, and morphing.
Alignment is the mapping of points from a first, "source" coordinate system, in which, say, a prototype object is described, into another, "target" coordinate system, in which an object somehow related is described. A camera in an manufacturing apparatus, for instance, may produce a two-dimensional image of a part waiting to be drilled. The image is expressed in terms of the target coordinate system, to which the drill-positioning system responds. The manufacturing apparatus, on the other hand, stores an internal model of a prototype of the part in terms of a source coordinate system, in which the locations to be drilled are also expressed. In order to drill the real-world part properly, the source coordinates of the model's holes must be mapped to target coordinates at which the drilling is actually to occur: the model and the real-world part must be aligned.
Alignment is also a first step in morphing, in which intermediate images are generated to make an object in a given first, source image metamorphose into a given second, target image. In each intermediate image, a point corresponding to a point in the source image is positioned by interpolating between a source-image point and a point in the target image with which the alignment process has associated the source-image point.
A related problem is object recognition, in which the task is to determine whether an object in an acquired image is of the type represented in an internal model.
All of these operations start with identification of feature points in the source and target images. These are typically the locations of edges, vertices, etc. that are of most visual interest. Generally inelegant but nonetheless workable methods that lend themselves to computer implementation have been used to identify feature points. But correspondences must then be assigned between feature points in the source image and those in the target image. To do this without human intervention is a problem.
The reason for this can readily be seen. The input to the correspondence-assignment process is feature data in the form of position coordinates, and there is almost never any direct relationship between the coordinates, in different images, of corresponding feature points. A number of attempts have accordingly been made to determine correspondences on the basis of feature-point descriptions that characterize different feature points in an image on the basis of their relationships to other feature points and the same image. A method described in Scott, "An Algorithm for Associating the Features of Two Patterns," Proc. Royal Society of London, pp. 21-26 (1991), employs eigenvectors of a "proximity description matrix," which describes Gaussian-weighted distances between point data. Shapiro et al., "Feature-Based Correspondence: an Eigenvector Approach," Image and Vision Computing, 10(5): 283-88, June 1992, describes a further development of this method.
This proximity method effectively assigns correspondences in some circumstances, but it is not information-preserving; i.e., the feature locations cannot be recovered from the description matrix. Moreover, the results of the computations that it employs are of limited value in morphing, alignment, or other processes of which correspondence determination is a prerequisite.